package com.ggqq.day315;
// 1552 https://leetcode-cn.com/problems/magnetic-force-between-two-balls/
import java.util.Arrays;

public class ball {
    public static void main(String[] args){
        int[] position = {5,4,3,2,1,1000000000};
        ball b = new ball();
        int s = b.maxDistance(position, 2);
        System.out.println(s);
    }

    public int maxDistance(int[] position, int m) {
        //对答案进行二分查找。（先排好序）
        Arrays.sort(position);
        int left = 1,right = position[position.length-1]-position[0],ans=-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(check(mid,position,m)){//mid为中间的值，m为插入球的个数
                ans = mid;   //mid 合法
                left =mid+1;
            }else{
                right = mid-1;//mid不合法
            }
        }
        return ans;
    }
    public boolean check(int x,int[] position,int m){
        int pre =position[0],cnt = 1;//cnt 是篮子里放球得个数
        for(int i=1;i<position.length;i++){
            if(position[i]-pre>=x){
                pre =position[i];
                cnt+=1;
            }
        }
        return cnt>=m;

    }
}
